
#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

// 75. Sort Colors
// https://leetcode.com/problems/sort-colors/description/
//
// 计数排序的思路
// 对整个数组遍历了两遍
// 时间复杂度: O(n)
// 空间复杂度: O(k), k为元素的取值范围
class Solution
{
public:
    void sortColors(vector<int> &nums)
    {
        // 计数
        int count[3] = {0}; // 存放0，1，2三个数字的数量

        // 遍历数组，计数
        for (int i = 0; i < nums.size(); i++)
        {
            // 防止下标越界，需要判断客户的输入
            assert(nums[i] >= 0 && nums[i] <= 2);
            count[nums[i]]++;
        }

        // cout<<"size of count: "<<sizeof(count)/sizeof(int)<<endl;
        // cout<<"size of count: "<<begin(count)<<endl;
        // cout<<"size of count: "<<end(count)<<endl;
        // cout<<"size of count: "<<end(count)-begin(count)<<endl;
        // 从头开始填数
        // int index = 0;
        // for (int i = 0; i < count[0]; i++)
        //     nums[index++] = 0;
        // for (int i = 0; i < count[1]; i++)
        //     nums[index++] = 1;
        // for (int i = 0; i < count[2]; i++)
        //     nums[index++] = 2;

        // 数组长度：(end(count)-begin(count))
        int index = 0;
        int sum = 0;
        for (int i = 0; i < (end(count) - begin(count)); i++)
        {
            sum += count[i];
            while (index < sum)
                nums[index++] = i;
        }
    }
};

int main()
{
    int nums[] = {2, 2, 2, 1, 1, 0};
    vector<int> vec = vector<int>(nums, nums + sizeof(nums) / sizeof(int));

    Solution().sortColors(vec);
    for (int i = 0; i < vec.size(); i++)
        cout << vec[i] << " ";
    cout << endl;
}